package exam.bak.E58;


import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class P3 {
    public boolean[] pathAvailable(int[][] matrix, int[][] starts, int[][] ends) {
        int len = starts.length;
        boolean[] result = new boolean[len];
        for (int i = 0; i < len; i++) {
            result[i] = bfs(matrix, starts[i], ends[i]);
        }
        return result;
    }

    private static int[][] directions = new int[][]{
            {-1, 0}, {1, 0}, {0, 1}, {0, -1}
    };

    private boolean bfs(int[][] matrix, int[] start, int[] end) {
        int len = matrix.length;
        int[][] board = new int[len][len];
        Queue<int[]> queue = new LinkedBlockingQueue<>();
        queue.add(new int[]{start[0], start[1]});
        board[start[0]][start[1]] = 1;
        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            if (node[0] == end[0] && node[1] == end[1]) {
                return true;
            } else {
                for (int[] direct : directions) {
                    int x = node[0] + direct[0];
                    int y = node[1] + direct[1];
                    if (0 <= x && x < len && 0 <= y && y < len && matrix[x][y] == 1 && board[x][y] == 0) {
                        board[x][y] = 1;
                        queue.add(new int[]{x, y});
                    }
                }
            }
        }
        return false;
    }


    public static void main(String[] args) {
        int[][] matrix = new int[][]{{1, 1, 1, 1}, {0, 0, 0, 0}, {1, 1, 1, 1}, {1, 1, 0, 1}};
        int[][] starts = new int[][]{{0, 0}, {0, 1}, {2, 0}};
        int[][] ends = new int[][]{{0, 3}, {2, 2}, {3, 3}};
        boolean[] booleans = new P3().pathAvailable(matrix, starts, ends);
        for (boolean flag : booleans) {
            System.out.println(flag);
        }
    }
}
